package swardToOffer.struct_1_arr;

/**
 * @Author ChanZany
 * @Date 2021/5/19 15:55
 * @Version 1.0
 * 长度为【n+1】的数组里所有数字都在【1~n】区间，
 * 找出数组中任意一个重复的数字，如
 * 长度为8的数组[2,3,5,4,3,2,6,7] ，对应的输出是2 or 3
 * 要求：不能修改数组
 * 分析：无法借助原有思路进行求解，
 * 解法1：借用HashMap解决
 * 解法2: 二分查找的思路: 如果数值在区间[begin,end]内的元素个数超过了end-begin+1,则说明在[begin,end]数值区间内
 * 一定有重复的元素。
 *
 */
public class DuplicatedNum2 {
    private int findDup(int[] nums){
        if (nums.length <= 0) return -1;
        int begin = 1;
        int end = nums.length-1;
        while (end >= begin){
            int middle = ((end-begin)>>1)+begin; //中位数
            int count = countRange(nums,begin,middle);
            if (end==begin){//结束条件，二分条件到end==begin时，若count>1，则返回begin or end
                if (count>1) return begin;
                else break;
            }
            if (count>(middle-begin+1)){//该区间内有重复元素
                end = middle;
            }else begin=middle+1;
        }
        return -1;
    }

    private int countRange(int[] nums, int begin, int end) {
        int count = 0;
        for (int num : nums) {
            if (begin<=num&& num<=end){
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {2,3,5,4,3,2,6,7};
        System.out.println(new DuplicatedNum2().findDup(nums));
    }

}
